from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 先锁定在那行，然后二分
        n = len(matrix)
        m = len(matrix[0])
        cnt = n - 1  # 初始化为 n-1 考虑到 target在最后一行中 for循环没有遍历到
        for i in range(n):
            if matrix[i][0] > target:
                cnt = i - 1
                break
        a = matrix[cnt][:]
        # print(a)
        l, r = -1, m - 1
        while l + 1 < r:
            mid = (l + r) // 2
            if a[mid] >= target:
                r = mid
            else:
                l = mid
        # r:表示 >= 的部分
        if a[r] == target:
            return True
        else:
            return False
